package com.sicheng.蓝桥.练习题.dp.数位;

import java.util.ArrayList;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/1 16:36
 */
public class Windy数 {
    /**
     * https://www.acwing.com/solution/content/15562/
     * Windy定义了一种Windy数:不含前导零且相邻两个数字之差至少为2的正整数被称为
     * Windy数。
     * Windy想知道，在A和B之间，包括A和B，总共有多少个Windy数?
     * 输入格式
     * I
     * 共一行，包含两个整数A和B。
     * 输出格式
     * 输出一个整数，表示答案。数据范围
     * 1<A<B≤2×10^9
     */

    //dp[i,j] i位，最高位是j的windy数的个数
    static long[][] dp = new long[15][10];

    static void init() {
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1;
        }

        for (int i = 2; i <= 10; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    if (Math.abs(j - k) >= 2)
                        dp[i][j] += dp[i - 1][k];
                }
            }
        }
    }


    static long dp(int n) {
        if (n == 0)
            return 0;
        long res = 0;
        long last = -2;
        ArrayList<Integer> nums = new ArrayList<>();
        while (n > 0) {
            nums.add(n % 10);
            n /= 10;
        }

        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums.get(i);
            for (int j = i == nums.size() - 1 ? 1 : 0; j < x; j++) {
                if (Math.abs(j - last) >= 2)
                    res += dp[i + 1][j];
            }
            if (Math.abs(x - last) < 2)
                break;

            last = x;

            if (i == 0)
                res++;
        }

        //特判 低位
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 1; j <= 9; j++) {
                res += dp[i][j];
            }
        }
        return res;
    }

    public static void main(String[] args) {

    }


}
